1. Field of the Invention
The invention relates generally to reducing the burden placed on computer systems and more specifically to reducing the overhead of virtual method invocations.
2. Description of Related Art
Since the advent of computers, computer scientists and engineers have strived to make computers faster. Programming languages such as object-oriented programming languages (e.g., Java, C++, etc.) create additional burden on a computer system through invocation of virtual method calls which affects the time involved in executing program instructions. Virtual method calls cannot be easily eliminated because the compiler is unaware of which callee of the virtual method callee (xe2x80x9ccalleexe2x80x9d) will be invoked. Invoking a callee depends upon the class hierarchy being used. Class hierarchy is a way of organizing information in which related classes are connected in a tree-like structure. FIGS. 1 and 2 illustrate two simple class hierarchies that show how a callee is invoked. FIG. 1 illustrates a simple class hierarchy in which xe2x80x9cAxe2x80x9d is a superclass of xe2x80x9cBxe2x80x9d. The arrow from class B to A means that A is a superclass of B as in FIG. 1. Invoking a call to foo for xe2x80x9cBxe2x80x9d objects should invoke xe2x80x9cA""sxe2x80x9d foo method. Foo is a function call. A function call may include parameters such as a subroutine or may be without parameters such as a function. Using the principle presented in FIG. 1, FIG. 2 illustrates another class hierarchy that is slightly more complex in which A is a superclass of B and B is a superclass of C. C_object is converted to type xe2x80x9cBxe2x80x9d and is passed to method bar ( ). Method bar ( ) is a name of a function. In method bar ( ), b_object.foo ( ) invokes xe2x80x9cC""sxe2x80x9d foo method instead of xe2x80x9cA""sxe2x80x9d foo method. If xe2x80x9cA""sxe2x80x9d foo method is the correct callee but xe2x80x9cC""sxe2x80x9d foo was invoked instead, the method is inaccurate because the wrong foo was called.
Inlining is a technique used in compilers to reduce the overhead of method invocations by replacing a call site (i.e., a call instruction) with the method body of the callee. When inlining a virtual method, multiple instances of the method may be invoked. Compilers, therefore, must ensure that the right instance of the method is executed. There are generally two conventional inlining approaches that may be used to reduce virtual method calls: (1) checking virtual tables as illustrated in FIG. 4, and (2) checking foo addresses as illustrated in FIG. 6.
In order to understand these two conventional approaches, object layouts, which directly influences inlining, are explained. FIG. 3 depicts the object layout used in most implementations of object-oriented languages (e.g., C++, Java, etc.). Reference x points to an object 200. As shown in FIG. 3, object 200 contains data 205 of the object 200 such as different types of fields, integer floating points, other types of pointers, or other data. The first field to which the object points is the virtual method table (xe2x80x9cvtablexe2x80x9d) 210. Vtable 210 contains all of the function pointer entries. More specifically, for each virtual method of the object, there is a dedicated entry in the vtable pointing to the native code of the method. To access the address of a virtual method foo, the pointer must be dereferenced. Dereferencing involves retrieving information from an address by a pointer. The pointer indicates the location of the data. It will be appreciated that every time a dereference occurs, a memory access occurs. The first dereference accesses vtable 210 (t=[x]). xe2x80x9cTxe2x80x9d refers to the beginning point of vtable 210. The second dereference accesses the address of foo ([t+64]) 230. xe2x80x9cT +64xe2x80x9d is the amount of off-set from xe2x80x9ct.xe2x80x9d This entry of the reference accesses the actual native code object address which is foo. Vtable also contains entries pointing to other methods such as bar 220.
As the virtual method gets inlined, the compiler such as a just-in-time (JIT) compiler generates a run-time test to verify if the inlined callee is the right instance to be invoked. The typical method invocation code sequence is executed if the verification fails. The run-time test is typically implemented by checking the vtable 210 or by checking foo of the actual target address of the method invocation. Checking the vtable 210 involves comparing the object""s vtable 210 with the vtable of the class of the inlined method. If the comparison is successful (i.e., object 200 matches the vtable of the class of the inlined method), it is safe to execute the inlined code because the inlined method will be dynamically dispatched at runtime. If the comparison fails (i.e., object 200 does not match the vtable of the class of the inlined method), the conventional dispatching code sequence is executed to invoke the virtual method call. FIG. 5 shows the iA32 native code sequence. For clarity, the control flow graph of the inlined code is depicted in FIG. 4. The conventional dispatching code is shown at 410 of FIG. 4. The benefit of this conventional approach is that only one memory access ([x]) 400 is involved to determine if either xe2x80x9cA""sxe2x80x9d foo is inlined at operation 420 or the conventional call sequence 410 should be executed as illustrated in FIG. 4. For instance, if [x] =xe2x80x9cA""sxe2x80x9d vtable, xe2x80x9cA""sxe2x80x9d foo is inlined at operation 420. Additionally, only one comparison must be performed of the vtable address, and one comparison of the branch to the vtable (e.g., branch to the inline version). But one drawback to this conventional approach is that checking the vtable is conservative and less accurate. For example, referring to FIG. 2, if xe2x80x9cxxe2x80x9d is always a type B class, the checking always fails because xe2x80x9cAxe2x80x9d and xe2x80x9cBxe2x80x9d objects have distinct vtables. More specifically, xe2x80x9cAxe2x80x9d is a superclass of xe2x80x9cBxe2x80x9d and xe2x80x9cCxe2x80x9d. xe2x80x9cC""sxe2x80x9d object is xe2x80x9cBxe2x80x9d""s object and xe2x80x9cA""sxe2x80x9d object, but not vice versa. After this process, FIG. 4 shows a merge point occurs at 430. A merge point is where the computer program returns to another operation that may be unrelated to an inlining operation.
The second conventional approach illustrated in FIG. 6 relates to inserting code to compare the actual method address that x.foo ( ) is invoking with the address of xe2x80x9cA""sxe2x80x9d foo. Although the second conventional approach is more precise at inlining xe2x80x9cA""sxe2x80x9d foo 520 than the first conventional approach, checking the target address requires at least two memory accesses (i.e., [x] and [t+64]) such as operations 500, 510. In JIT compiler, a method is compiled before its first execution. If A""s foo is not yet compiled, the actual address of A""s foo is unknown. The JIT compiler then allocates memory space in which to fill the address of A""s foo as soon as A""s foo is compiled. In such a circumstance, the test requires 3 memory accesses. FIG. 7 shows the iA32 native code sequence that implements this approach. OXBE762Ch is the address of the place holding the address of the inlined method. It is therefore desirable to have a method that reduces the number of memory accesses and improves accuracy of inlining a method bar.